#include <iostream>
#include <stack>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{

public:
    bool GetPath(TreeNode *root, TreeNode *x, stack<TreeNode *> &st)
    {
        if (root == nullptr)
        {
            return false;
        }
        st.push(root);
        if (root == x)
        {
            return true;
        }
        if (GetPath(root->left, x, st))
        {
            return true;
        }
        if (GetPath(root->right, x, st))
        {
            return true;
        }
        st.pop();
        return false;
    }
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        stack<TreeNode *> pPath, qPath;
        GetPath(root, p, pPath);
        GetPath(root, q, qPath);
        while (pPath.size() != qPath.size())
        {
            if (pPath.size() > qPath.size())
            {
                pPath.pop();
            }
            else
            {
                qPath.pop();
            }
        }
        while (qPath.top() != pPath.top())
        {
            qPath.pop();
            pPath.pop();
        }
        return qPath.top();
    }
};